package com.since.data_structure.hash;

/**
 * Created by Sincerity on 2020/5/16.
 * 描述： 数组+链表
 */
public class HashTable {
    private HashLinkedList[] hashArray;
    private int maxSize;

    public HashTable(int maxSize) {
        hashArray = new HashLinkedList[maxSize];
        for (int i = 0; i < maxSize; i++) {
            hashArray[i] = new HashLinkedList();
        }
        this.maxSize = maxSize;
    }

    /**
     * 添加一个节点
     *
     * @param node 需要添加的节点
     */
    public void add(HashLinkedListNode node) {
        int hash = hash(node.id);
        hashArray[hash].add(node);
    }

    public int delete(int no) {
        int hash = hash(no);
        return hashArray[hash].delete(no);
    }

    /**
     * 通过下标过去元素
     *
     * @param no 编号
     * @return 返回查找到的节点
     */
    HashLinkedListNode get(int no) {
        int hash = hash(no);
        return hashArray[hash].get(no);
    }

    /**
     * 获取hash表中所有元素信息
     */
    void show() {
        for (int i = 0; i < maxSize; i++) {
            hashArray[i].show(i);
        }
    }

    /**
     * 返回桶的下标 模拟求hash值方法
     *
     * @param vale 需要求hash值得元素
     * @return 当前元素的hash值
     */
    private int hash(int vale) {
        return vale % maxSize;
    }

    /**
     * 散列桶
     */
    class HashLinkedList {
        HashLinkedListNode head;

        /**
         * 给链表添加节点
         *
         * @param node 需要添加的节点
         */
        public void add(HashLinkedListNode node) {
            if (head == null) {
                head = node;
                return;
            }
            //头节点不为空
            HashLinkedListNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }

        /**
         * 遍历链表信息
         *
         * @param no 链表的节点
         */
        void show(int no) {
            if (head == null) {
                return;
            }
            System.out.print("第 " + (no + 1) + " 链表的信息为");
            HashLinkedListNode temp = head;
            while (temp != null) {
                System.out.printf(" => id=%d name=%s\t", temp.id, temp.name);
                temp = temp.next;
            }
            System.out.println();
        }

        /**
         * 获取id所在的节点
         *
         * @param id id
         * @return 返回id所在的节点
         */
        HashLinkedListNode get(int id) {
            if (head == null) {
                return null;
            }
            HashLinkedListNode temp = head;
            while (temp != null) {
                if (temp.id == id) {
                    return temp;
                }
                temp = temp.next;
            }
            return null;
        }

        public int delete(int no) {
            if (head == null) {
                return -1;
            }
            HashLinkedListNode temp = head;
            HashLinkedListNode next = temp.next;
            while (temp != null) {
                if (temp.id == no) {
                    head = head.next;
                }
                temp = temp.next;
            }
            head = null;
            return -1;
        }
    }

    static class HashLinkedListNode {
        int id;
        String name;
        HashLinkedListNode next;

        public HashLinkedListNode(int id, String name) {
            this.id = id;
            this.name = name;
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        @Override
        public String toString() {
            return "HashLinkedListNode{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
}
